package com.cat.dataStructure03;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-the-number-of-incremovable-subarrays-ii/
 * @create 2025/11/10 14:58
 * @since JDK17
 */

class Solution35 {
    public long incremovableSubarrayCount(int[] nums) {
        // 可以移除多少个后缀
        // 核心思路 : 这个前缀必须单调递增
        int n = nums.length, i = 0;
        while (i < n - 1 && nums[i] < nums[i + 1]) {
            i++;
        }
        if (i == n - 1) {
            return (long) n * (n + 1) / 2;
        }
        long ans = i + 2;
        for (int j = n - 1; j == n - 1 || nums[j] < nums[j + 1]; j--) {
            while (i >= 0 && nums[i] >= nums[j]) {
                i--;
            }
            ans += i + 2;
        }

        return ans;
    }
}